#include <iostream>
#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// class Solution {
//     vector<int> vec;
// public:
//     bool isValidBST(TreeNode* root) {
//         if(!root) return true;
//         dfs(root);
//         for(int i = 0;i < vec.size() - 1;)
//         {
//             if(vec[i] >= vec[++i]) return false;
//         }
//         return true;
//     }
//     void dfs(TreeNode* root)
//     {
//         if(root == NULL) return;
//         if(root->left != NULL)
//         {
//             dfs(root->left);
//             // vec.push_back(root->left->val);
//         }
//         vec.push_back(root->val);
//         if(root->right != NULL)
//         {
//             dfs(root->right);
//             // vec.push_back(root->right->val);
//         }
//     }
// };

// class Solution {
// public:
//     bool isValidBST(TreeNode* root, TreeNode *min = nullptr, TreeNode *max = nullptr) {
//         if (!root) return true;
//         if (min != NULL && root->val <= min->val) return false;
//         if (max != NULL && root->val >= max->val) return false;
//         return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
//     }
// };

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        TreeNode *pre = nullptr;
        vector<TreeNode*> worker;
        while (root || worker.size()) {
            while (root) {
                worker.push_back(root);
                root = root->left;
            }
            root = worker.back(), worker.pop_back();
            if (pre && pre->val >= root->val) return false;
            pre = root, root = root->right;
        }
        return true;
    }
};


int main()
{
    TreeNode h1(2);
    TreeNode h2(1);
    TreeNode h3(3);
    h1.left = &h2;
    h1.right = &h3;
    Solution sol;
    cout << sol.isValidBST(&h1) << endl;
}